package class19;

import java.util.HashMap;

// 本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
public class Code03_StickersToSpellWord {

	/**
	 * 计算拼出目标字符串所需的最少贴纸数量
	 * 
	 * @param stickers 所有可用的贴纸，每种贴纸都有无限张
	 * @param target 需要拼出的目标字符串
	 * @return 最少需要的贴纸数量，如果无法拼出则返回-1
	 */
	public static int minStickers1(String[] stickers, String target) {
		int ans = process1(stickers, target);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 使用暴力递归方法计算拼出目标字符串所需的最少贴纸数量
	 * 
	 * @param stickers 所有可用的贴纸
	 * @param target 当前需要拼出的目标字符串
	 * @return 最少需要的贴纸数量，如果无法拼出则返回Integer.MAX_VALUE
	 */
	public static int process1(String[] stickers, String target) {
		// 基础情况：如果目标字符串为空，则不需要任何贴纸
		if (target.length() == 0) {
			return 0;
		}
		
		// 初始化最小贴纸数为最大值
		int min = Integer.MAX_VALUE;
		
		// 尝试每一张贴纸作为第一张贴纸
		for (String first : stickers) {
			// 计算使用当前贴纸后剩余的字符串
			String rest = minus(target, first);
			
			// 如果使用贴纸后字符串有变化（说明有字符被消掉）
			if (rest.length() != target.length()) {
				// 递归计算剩余字符串需要的最少贴纸数
				min = Math.min(min, process1(stickers, rest));
			}
		}
		
		// 返回结果：如果min仍为最大值说明无法拼出，否则返回min+1（加上当前使用的贴纸）
		return min + (min == Integer.MAX_VALUE ? 0 : 1);
	}

	/**
	 * 计算字符串s1减去字符串s2后剩余的字符
	 * 
	 * @param s1 原始字符串
	 * @param s2 需要减去的字符串
	 * @return s1中减去s2中字符后剩余的字符串
	 */
	public static String minus(String s1, String s2) {
		// 将字符串转换为字符数组
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		
		// 统计s1中每个字符的出现次数
		int[] count = new int[26];
		for (char cha : str1) {
			count[cha - 'a']++;
		}
		
		// 减去s2中每个字符的出现次数
		for (char cha : str2) {
			count[cha - 'a']--;
		}
		
		// 构建剩余字符串
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < 26; i++) {
			if (count[i] > 0) {  // 如果字符还有剩余
				for (int j = 0; j < count[i]; j++) {
					builder.append((char) (i + 'a'));  // 将剩余字符添加到结果中
				}
			}
		}
		return builder.toString();
	}

	/**
	 * 使用优化方法计算拼出目标字符串所需的最少贴纸数量
	 * 
	 * @param stickers 所有可用的贴纸
	 * @param target 需要拼出的目标字符串
	 * @return 最少需要的贴纸数量，如果无法拼出则返回-1
	 */
	public static int minStickers2(String[] stickers, String target) {
		int N = stickers.length;
		// 关键优化：用词频表替代贴纸数组，统计每张贴纸中各字符的出现次数
		int[][] counts = new int[N][26];
		for (int i = 0; i < N; i++) {
			char[] str = stickers[i].toCharArray();
			for (char cha : str) {
				counts[i][cha - 'a']++;
			}
		}
		
		int ans = process2(counts, target);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 使用词频表优化的递归方法
	 * 
	 * @param stickers 词频表，统计每张贴纸中各字符的出现次数
	 * @param t 当前需要拼出的目标字符串
	 * @return 最少需要的贴纸数量，如果无法拼出则返回Integer.MAX_VALUE
	 */
	public static int process2(int[][] stickers, String t) {
		// 基础情况：如果目标字符串为空，则不需要任何贴纸
		if (t.length() == 0) {
			return 0;
		}
		
		// 对目标字符串做词频统计
		char[] target = t.toCharArray();
		int[] tcounts = new int[26];
		for (char cha : target) {
			tcounts[cha - 'a']++;
		}
		
		int N = stickers.length;
		int min = Integer.MAX_VALUE;
		
		// 尝试每一张贴纸
		for (int i = 0; i < N; i++) {
			int[] sticker = stickers[i];
			
			// 最关键的优化(重要的剪枝!这一步也是贪心!)
			// 只有当贴纸包含目标字符串的第一个字符时才考虑使用这张贴纸
			if (sticker[target[0] - 'a'] > 0) {
				// 计算使用当前贴纸后剩余的字符串
				StringBuilder builder = new StringBuilder();
				for (int j = 0; j < 26; j++) {
					if (tcounts[j] > 0) {  // 如果目标字符串中还有字符j
						// 计算使用贴纸后字符j的剩余数量
						int nums = tcounts[j] - sticker[j];
						for (int k = 0; k < nums; k++) {
							builder.append((char) (j + 'a'));  // 添加剩余的字符到结果中
						}
					}
				}
				
				String rest = builder.toString();
				// 递归计算剩余字符串需要的最少贴纸数
				min = Math.min(min, process2(stickers, rest));
			}
		}
		
		// 返回结果：如果min仍为最大值说明无法拼出，否则返回min+1（加上当前使用的贴纸）
		return min + (min == Integer.MAX_VALUE ? 0 : 1);
	}

	/**
	 * 使用记忆化搜索优化的方法计算拼出目标字符串所需的最少贴纸数量
	 * 
	 * @param stickers 所有可用的贴纸
	 * @param target 需要拼出的目标字符串
	 * @return 最少需要的贴纸数量，如果无法拼出则返回-1
	 */
	public static int minStickers3(String[] stickers, String target) {
		int N = stickers.length;
		// 统计每张贴纸中各字符的出现次数
		int[][] counts = new int[N][26];
		for (int i = 0; i < N; i++) {
			char[] str = stickers[i].toCharArray();
			for (char cha : str) {
				counts[i][cha - 'a']++;
			}
		}
		
		// 使用记忆化搜索优化，dp存储已计算过的状态结果
		HashMap<String, Integer> dp = new HashMap<>();
		dp.put("", 0);  // 基础情况：空字符串需要0张贴纸
		
		int ans = process3(counts, target, dp);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 使用记忆化搜索的递归方法
	 * 
	 * @param stickers 词频表，统计每张贴纸中各字符的出现次数
	 * @param t 当前需要拼出的目标字符串
	 * @param dp 记忆化搜索的缓存表
	 * @return 最少需要的贴纸数量，如果无法拼出则返回Integer.MAX_VALUE
	 */
	public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
		// 如果已经计算过该状态，直接返回结果
		if (dp.containsKey(t)) {
			return dp.get(t);
		}
		
		// 对目标字符串做词频统计
		char[] target = t.toCharArray();
		int[] tcounts = new int[26];
		for (char cha : target) {
			tcounts[cha - 'a']++;
		}
		
		int N = stickers.length;
		int min = Integer.MAX_VALUE;
		
		// 尝试每一张贴纸
		for (int i = 0; i < N; i++) {
			int[] sticker = stickers[i];
			
			// 关键剪枝：只有当贴纸包含目标字符串的第一个字符时才考虑使用这张贴纸
			if (sticker[target[0] - 'a'] > 0) {
				// 计算使用当前贴纸后剩余的字符串
				StringBuilder builder = new StringBuilder();
				for (int j = 0; j < 26; j++) {
					if (tcounts[j] > 0) {  // 如果目标字符串中还有字符j
						// 计算使用贴纸后字符j的剩余数量
						int nums = tcounts[j] - sticker[j];
						for (int k = 0; k < nums; k++) {
							builder.append((char) (j + 'a'));  // 添加剩余的字符到结果中
						}
					}
				}
				
				String rest = builder.toString();
				// 递归计算剩余字符串需要的最少贴纸数
				min = Math.min(min, process3(stickers, rest, dp));
			}
		}
		
		// 计算当前状态的结果
		int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
		// 将结果存入缓存
		dp.put(t, ans);
		return ans;
	}

}